//
// Created by mac on 2023/12/5.
//

// 汉诺塔问题
class Solution
{
private:
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        // 0、递归出口：只剩一个盘子的话就直接移动
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        // 1. 先把 a 柱上 n - 1 个盘子借助 c 移动到 b 柱
        dfs(A, C, B, n - 1);
        // 2. 再把 a 柱剩下的一个盘子直接移动到 c 柱
        C.push_back(A.back());
        A.pop_back();
        // 3. 最后再把 b 柱上的 n - 1 个盘子借助 a 移动到 c 柱
        dfs(B, A, C, n - 1);
    }

public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
    {
        dfs(A, B, C, A.size());
    }
};
